//给你一个由正整数组成的数组 nums 和一个 正 整数 k 。 
//
// 如果 nums 的子集中，任意两个整数的绝对差均不等于 k ，则认为该子数组是一个 美丽 子集。 
//
// 返回数组 nums 中 非空 且 美丽 的子集数目。 
//
// nums 的子集定义为：可以经由 nums 删除某些元素（也可能不删除）得到的一个数组。只有在删除元素时选择的索引不同的情况下，两个子集才会被视作是不同的
//子集。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [2,4,6], k = 2
//输出：4
//解释：数组 nums 中的美丽子集有：[2], [4], [6], [2, 6] 。
//可以证明数组 [2,4,6] 中只存在 4 个美丽子集。
// 
//
// 示例 2： 
//
// 
//输入：nums = [1], k = 1
//输出：1
//解释：数组 nums 中的美丽数组有：[1] 。
//可以证明数组 [1] 中只存在 1 个美丽子集。 
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 18 
// 1 <= nums[i], k <= 1000 
// 
//
// Related Topics 数组 哈希表 数学 动态规划 回溯 组合数学 排序 👍 59 👎 0


package LeetCode.editor.cn;


/**
 * @author ldltd
 * @date 2025-03-07 09:26:14
 * @description 2597.美丽子集的数目
 
 */
 
public class TheNumberOfBeautifulSubsets {
    public static void main(String[] args) {
    //测试代码
    TheNumberOfBeautifulSubsets fun = new TheNumberOfBeautifulSubsets();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)
public class Solution {
    private int res = 0; // 用于记录美丽子集的数量

    public int beautifulSubsets(int[] nums, int k) {
        int[] count = new int[1001]; // 用于记录当前子集中是否包含某个数字
        dfs(nums, k, count, 0); // 从索引 0 开始深度优先搜索
        return res - 1; // 减去空集
    }

    private void dfs(int[] nums, int k, int[] count, int ind) {
        if (ind == nums.length) {
            res++; // 找到一个有效的子集
            return;
        }

        // 不选择当前数字 nums[ind]
        dfs(nums, k, count, ind + 1);

        // 选择当前数字 nums[ind]，检查是否满足条件
        if (nums[ind] - k < 0 || count[nums[ind] - k] == 0) {
            if (nums[ind] + k > 1000 || count[nums[ind] + k] == 0) {
                count[nums[ind]]++; // 标记当前数字已被使用
                dfs(nums, k, count, ind + 1); // 递归处理下一个数字
                count[nums[ind]]--; // 回溯，取消标记
            }
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
